Інформація про навчальний заклад

ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано

Інформація про роботу

Рік:
1998
Тип роботи:
Задача
Предмет:
Системи автоматизованого проектування ЗВТ

Частина тексту файла

МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ Державний університет “Львівська політехніка” АЛГОРИТМ РІШЕННЯ ЗАДАЧІ КОМІВОЯЖЕРА І Н С Т Р У К Ц І Я до лабораторної роботи № 3 з курсу “Дискретні моделі в САПР” для базового напрямку 6.0804 “Комп’ютерні науки” Затверджено: на засіданні кафедри “Системи автоматизованого провектування” Протокол N 14 від 03.04.1997 р. Львів - 1998 Алгоритм рішення задачі комівояжера. Інструкція до лабораторної роботи N3 з курсу “Дискретні моделі в САПР” для базового напрямку 6.0804 “Комп’ютерні науки” /Склали: В.І.Каркульовський, С.П.Ткаченко, І.І.Чура. -Львів: ДУ “Львівська політехніка”, 1998. Укладачі: В.І.Каркульовський, канд.техн.наук, доц., С.П.Ткаченко, канд.техн.наук, доц. І.І.Чура, канд.техн.наук, доц.. Відповідальний за випуск: Д.В.Федасюк, канд.техн.наук, доц. Рецензенти: Стех Ю.В. , канд.техн.наук, доц. Мотика І.І. , канд.техн.наук, доц. 1. МЕТА РОБОТИ Метою даної лабораторної роботи є вивчення і дослідження алгоритмів рішення задачі комівояжера. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ ФОРМУЛЮВАННЯ ТА ДЕЯКІ ВЛАСТИВОСТІ ЗАДАЧІ КОМІВОЯЖЕРА Комівояжеру потрібно відвідати кожне місто в певній зоні обслуговування і повернутися додому. Відомо, що комівояжеру хотілось би вибрати такий порядок обходу клієнтів, при якому його шлях був би найкоротшим. Таким чином, комівояжер зтикається із задачою пошуку маршрута мінімальної довжини, тривалості чи вартості. Задача комівояжера може бути сформульована, як задача на графі. Для цього необхідно побубувати граф G=(X,A), вершини якого відповідають містам в зоні комівояжера, а ребра(дуги) відображають комунікації, що з’єднують пари міст. Довжина a=(x,y)0 кожної дуги (x,y)A може бути рівна відстані, вартості чи часу або числовому значенню деякого комплексного критерію. Контур, що включає кожну вершину графа G хоча б один раз, називають маршрутом комівояжера. Контур, який включає кожну вершину графа G рівно один раз називають гамільтоновим. Загальною задачею комівояжера називають задачу пошуку маршруту найменшої довжини. Задачею комівояжера називають задачу пошуку гамільторового контура найменшої довжини. Контур комівояжера, який має найменшу довжину, називають оптимальним гамільтоновим контуром він є оптимальним рішенням задачі комівояжера. Оптимальний маршрут комівояжера не обов`язково є гамільтоновим контуром. Виникає питання, в яких випадках гамільтоновий контур є рішенням загальної задачі комівояжера? Відповідь дає наступна теорема. Теорема 1. Якщо для кожної пари вершин (х,у) виконується умова: a(x,y)a(x,z)+a(z,y) , для всіх zxy. (1) то гамільтоновий контур є рішенням загальної задачі комівояжера на графі G (якщо рішення задачі взагалі існує). Умова (1) говорить лише про те, що відстань безпосередньо від х до у ніколи не перевищує відстані від х до у через будь-яку іншу вершину z. Умову (1) називають нерівностю трикутника. УМОВИ ІСНУВАННЯ ГАМІЛЬТОНОВОГО КОНТУРУ. НИЖНІ ГРАНИЦІ. Рішенням задачі комівояжера є оптимальний гамільтоновий контур. Нажаль, не всі графи містять гамільтоновий контур. Отже перед тим, ніж перейти до пошуку оптимального гамільтонового контура потрібно довести факт його існування в даному графі. Введемо ряд визначень, які в подальшому нам знадобляться. Граф називається сильно зв`язаним, якщо в ньому для будь-яких двох вершин “х” і “у” існує шлях від “х” до “у”. Підмножина вершин Х деякого графа називається сильно зв`язаною, якщо для будь-яких пар вершин х Х і у Х існує шлях з “х” в “у” і Х не є підмножиною ніякої іншої множини вершин, які володіють тими ж властивостями. Сформулюємо загальну теорему Гуйя-Урі. Теорема 2. Якщо граф G(X,A) задовільняє умовам : 1) граф G силно зв’язаний ; 2) d(х)n для всіх х ( Х, де d(x) - степінь вершини х, п - кількість вершин, то він містить гамільтоновий контур. На практиці достатньо легко встановити, чи задовільняє деякий граф умовам (I.) і (II.) теореми 2. Умова (1.) перевіряється застосуванням до кожної пари вершин алгоритма Флойда або алгоритма Данцига для поб...
Антиботан аватар за замовчуванням

17.07.2020 15:07

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини